package 线索化二叉树;


public class 线索化二叉树 {
	public static void main(String[] args) {
		/*
		 *       1
		 *     /   \
		 *    3     6
		 *   / \   /
		 *  8  10 14 
		 *  
		 *  中序遍历：8,3,10,1,14,6
		 */
		TreeNode node = new TreeNode(1, "1");
		TreeNode node2 = new TreeNode(3, "3");
		TreeNode node3 = new TreeNode(6, "6");
		TreeNode node4 = new TreeNode(8, "8");
		TreeNode node5 = new TreeNode(10, "10");
		TreeNode node6 = new TreeNode(14, "14");
		node.left = node2;
		node.right = node3;
		node2.left = node4;
		node2.right = node5;
		node3.left = node6;
		
		//创建树
		ThreadedBinaryTree tree = new ThreadedBinaryTree();
		tree.setRoot(node);
		//线索化
		tree.threadeNode();
//		tree.midOrder(tree.root);
		
		//验证，中序：8,3,10,1,14,6 ；值10为node5结点，前驱是值3为node2的结点
		TreeNode nodeLeft = node5.left;
		TreeNode nodeRight = node5.right;
		System.out.println("值为10的结点前驱为："+nodeLeft);
		System.out.println("值为10的结点后继为："+nodeRight);
		
		//遍历线索化二叉树
		tree.threadedMidOrder();
		
	}
}


/**
 * 线索化二叉树，表示利用了结点的左右指针，指向遍历顺序的前驱和后继
 * @author PC
 */
class ThreadedBinaryTree {
	//根节点
	public TreeNode root;
	
	//辅助结点，指向当前结点前驱
	public TreeNode preNode;
	
	//初始化
	public ThreadedBinaryTree() {
		super();
	}
	//初始化根节点，设置哪个结点是根节点
	public void  setRoot(TreeNode root) {
		this.root = root;
	}
	
	/**
	 * 重载threadeNode()，直接使用
	 */
	public void threadeNode() {
		threadedNode(root);
	}

	/**
	 * 线索化二叉树，中序
	 * @param root
	 */
	public void threadedNode(TreeNode root) {
		//空则返回，说明上一层可以输出了，return和方法结束都表示跳出这层递归
		if(root == null) {
			return;
		}
		
		//遍历左子树
		threadedNode(root.left);
		
		//中序遍历，线索化二叉树，找到前驱，修改状态
		if(root != null && root.left == null) {
			root.left = preNode;
			root.leftType = 1;
		}
		//修改前驱结点的后继，遍历第一个结点没有前驱，并修改状态
		if(preNode != null && preNode.right == null) {
			preNode.right = root;
			preNode.rightType = 1;
		}
		//修改preNode，将当前结点赋给preNode，让它保持是下一个结点的前驱结点
		preNode = root;
		
		//遍历右子树
		threadedNode(root.right);
	}
	
	/**
	 * 中序遍历线索化二叉树
	 */
	public void threadedMidOrder() {
		System.out.println("遍历线索化二叉树...");
		TreeNode node = root;
		while(node != null) {
			//找到最左边第一个结点
			while(node.leftType == 0) {
				node = node.left;
			}
			//找到之后输出
			System.out.println(node);
			//如果当前结点右指针是线索结点（rightType=1）表示指向后继结点，是链接过去的，不是子树
			//一直输出后继
			while(node.rightType == 1) {
				node = node.right;
				System.out.println(node);
			}
			//一直找到不是后继结点的结点，是一个右子树，就把右子树如给当前结点，重新找后继
			node = node.right;
		}
		
	}
	
	/**
	 * 前序遍历
	 * 这个方法是结点中的方法，其他都是树中的方法
	 */
	public void nodePreOrder() {
		System.out.println("结点中的前序遍历...");
		if(root != null) {
			root.preOrder();
		}else {
			System.out.println("空树，无法遍历...");
		}
	}

	/**
	 * 前序遍历（中左右）
     * output:A-B-D-E-C-F
     * 另外一种写法，在TreeNode类中写方法，可以直接使用this.left.preOrder()
	 * @param root 参数是根节点
	 */
	public void preOrder(TreeNode root) {
		if(root == null) {
			return;
		}else {
			System.out.println(root.data);
			preOrder(root.left);
			preOrder(root.right);
		}
	}

	/**
	 * 中序遍历（左中右）
     * output:D-B-E-A-F-C
	 * @param root
	 */
	public void midOrder(TreeNode root) {
		if(root == null) {
			return;
		}else {

			midOrder(root.left);
			System.out.println(root.data);
			midOrder(root.right);
		}
	}
	
	/**
	 * 后序遍历（左右中）
     * output:D-E-B-F-C-A
	 * @param root
	 */
	public void postOrder(TreeNode root) {
		if(root == null) {
			return;
		}else {
			postOrder(root.left);
			postOrder(root.right);
			System.out.println(root.data);
		}
	}

	/**
	 * 前序遍历查找，好像只能再结点中写方法，这里不能掉root.left.preOrderSearch()
	 * @param data
	 * @return
	 */
	public  TreeNode preOrderSearch(Object data) {
//		System.out.println("前序遍历查找...");
//		//判断当前结点是不是
//		if(root.data == data) {
//			return root;
//		}
//		//左子树遍历查找
//		//接受结果的结点resNode
//		TreeNode resNode = null;
//		if(root.left != null) {
//		}
//		return null;
		
		//使用
		if(root != null) {
			return root.preOrderSearch(data);
		}else {
			return null;
		}
	}
	
	/**
	 * 中序查找使用
	 * @param data
	 * @return
	 */
	public TreeNode midOrderSearch(Object data) {
		if(root != null) {
			return root.midOrderSearch(data);
		}else {
			return null;
		}
	}
	
	/**
	 * 后序查找使用
	 * @param data
	 * @return
	 */
	public TreeNode postOrderSearch(Object data) {
		if(root != null) {
			return root.postOrderSearch(data);
		}else {
			return null;
		}
	}
	
	/**
	 * 递归删除使用，需要先判断是否是root结点
	 * @param data
	 */
	public void delNode(Object data) {
		if(root != null) {
			//如果只有一个结点，需要判断是否是这个节点
			if(root.data == data) {
				root = null;
			}else {
				//不是，递归删除
				root.delNode(data);
			}
		}else {
			System.out.println("空树...");
		}
	}
	
}

/**
 * 结点
 * 线索化二叉树结点，添加两个状态属性
 * 注意：这里使用的都是public的属性，方便取值赋值
 * 注意泛型的使用，data是数据，不同于结点，它可以存放其他数据，而left和right都是 结点 
 * class TreeNode<T> {
		public int index;
		public T data;
		public TreeNode<T> left;
		public TreeNode<T> right;
 * @author PC
 *
 */

class TreeNode {
	public int index;
	public Object data;
	public TreeNode left;
	public TreeNode right;
	//0表示左或右子树，1表示前驱或后继
	public int leftType;
	public int rightType;
	
	public TreeNode() {
		super();
	}
	public TreeNode(int index, Object data) {
		super();
		this.index = index;
		this.data = data;
	}
	@Override
	public String toString() {
		return "TreeNode [index=" + index + ", data=" + data + "]";
	}
	
	/**
	 * 前序遍历
	 */
	public void preOrder() {
		//输出根
		System.out.println(this);
		//左子树
		if(this.left != null) {
			this.left.preOrder();
		}
		//右子树
		if(this.right != null) {
			this.right.preOrder();
		}
	}
	
	/**
	 * 前序遍历查找
	 * @param data
	 * @return
	 */
	public TreeNode preOrderSearch(Object data) {
		System.out.println("前序遍历查找...");
		//判断是否当前结点
		if(this.data == data) {
			return this;
		}
		//左子树遍历查找
		//resNode用来存结果
		TreeNode resNode = null;
		if(this.left != null) {
			resNode = this.left.preOrderSearch(data);
		}
		//找到了就返回，没找到就找右子树
		if(resNode != null) {
			return resNode;
		}
		//没找到就找右子树
		if(this.right != null) {
			resNode = this.right.preOrderSearch(data);
		}
		return resNode;
	}
	
	/**
	 * 中序遍历查找
	 * @param data
	 * @return
	 */
	public TreeNode midOrderSearch(Object data) {
		TreeNode resNode = null;
		if(this.left != null) {
			resNode = this.left.midOrderSearch(data);
		}
		if(resNode != null) {
			return resNode;
		}
		
		System.out.println("中序遍历查找...");
		if(this.data == data) {
			return this;
		}
		
		if(this.right != null) {
			resNode = this.right.midOrderSearch(data);
		}
		return resNode;
	}
	
	/**
	 * 后序遍历查找
	 * @param data
	 * @return
	 */
	public TreeNode postOrderSearch(Object data) {
		TreeNode resNode = null;
		if(this.left != null) {
			resNode = this.left.postOrderSearch(data);
		}
		if(resNode != null) {
			return resNode;
		}
		
		if(this.right != null) {
			resNode = this.right.postOrderSearch(data);
		}
		
		System.out.println("后序遍历查找...");
		if(this.data == data) {
			return this;
		}
		return resNode;
	}
	
	/**
	 * 递归删除结点
	 * @param data
	 */
	public void delNode(Object data) {
		//注意：一定要判断左子结点是否为空，否则空指针异常
		if(this.left != null && this.left.data == data) {
			this.left = null;
			return;
		}
		//判断右子结点
		if(this.right != null && this.right.data == data) {
			this.right = null;
			return;
		}
		//都不是，左递归
		if(this.left != null) {
			this.left.delNode(data);
		}
		//都不是，右递归
		if(this.right != null) {
			this.right.delNode(data);
		}
	}
	
}